package com.lin.codesnippet.treeNome;

import lombok.Data;

/**
 * 二叉搜索树
 *
 * @param <T> 数据泛型
 */
public class BSTree<T extends Comparable<T>> {


    private BSTNode<T> mRoot;


    @Data
    public class BSTNode<T extends Comparable<T>> {
        T key;
        BSTNode<T> left;
        BSTNode<T> right;
        BSTNode<T> parent;

        public BSTNode() {
            super();
        }

        public BSTNode(T key, BSTNode<T> left, BSTNode<T> right, BSTNode<T> parent) {
            this.key = key;
            this.left = left;
            this.right = right;
            this.parent = parent;
        }
    }

    /**
     * 二叉搜索树递归查找
     *
     * @param x   跟节点
     * @param key 查找的数据
     * @return 查找到的节点
     */
    private BSTNode<T> search(BSTNode<T> x, T key) {
        if (x == null) {
            return x;
        }
        int cmp = key.compareTo(x.key);
        if (cmp < 0) {
            return search(x.left, key);
        } else if (cmp > 0) {
            return search(x.right, key);
        } else {
            return x;
        }
    }

    public BSTNode<T> search(T key) {
        return search(mRoot, key);
    }

    /**
     * 二叉搜索树非递归查找
     *
     * @param x   跟节点
     * @param key 查找的数据
     * @return 具备数据的节点
     */
    private BSTNode<T> iterativeSearch(BSTNode<T> x, T key) {
        while (x != null) {
            int cmp = key.compareTo(x.key);

            if (cmp < 0) {
                x = x.left;
            } else if (cmp > 0) {
                x = x.right;
            } else {
                return x;
            }
        }

        return x;
    }

    public BSTNode<T> iterativeSearch(T key) {
        return iterativeSearch(mRoot, key);
    }

    /**
     * 查找最大节点
     *
     * @param tree 跟节点
     * @return 最大节点
     */
    private BSTNode<T> maximum(BSTNode<T> tree) {
        if (tree == null) {
            return null;
        }

        while (tree.right != null) {
            tree = tree.right;
        }
        return tree;
    }

    /**
     * 查找最大节数据
     *
     * @return 最大节点
     */
    public T maximum() {
        BSTNode<T> p = maximum(mRoot);
        if (p != null) {
            return p.key;
        }

        return null;
    }

    /**
     * 查找最小节点
     *
     * @param tree 跟节点
     * @return 最小节点
     */
    private BSTNode<T> minimum(BSTNode<T> tree) {
        if (tree == null) {
            return null;
        }
        while (tree.left != null) {
            tree = tree.left;
        }
        return tree;
    }

    /**
     * 查找最小数据
     *
     * @return 最小节点
     */
    public T minimum() {
        BSTNode<T> p = minimum(mRoot);
        if (p != null) {
            return p.key;
        }

        return null;
    }

    /**
     * 查找前驱节点
     *
     * @param x 当前节点
     * @return 前驱节点
     */
    public BSTNode<T> predecessor(BSTNode<T> x) {
        // 如果x存在左孩子，则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。
        if (x.left != null) {
            return maximum(x.left);
        }
        // 如果x没有左孩子。则x有以下两种可能：
        // (01) x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。
        // (01) x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有右孩子"，找到的这个"最低的父结点"就是"x的前驱结点"。
        BSTNode<T> y = x.parent;
        while ((y != null) && (x == y.left)) {
            x = y;
            y = y.parent;
        }

        return y;
    }

    /**
     * 查找后继节点
     *
     * @param x 当前节点
     * @return 后继节点
     */
    public BSTNode<T> successor(BSTNode<T> x) {
        // 如果x存在右孩子，则"x的后继结点"为 "以其右孩子为根的子树的最小结点"。
        if (x.right != null) {
            return minimum(x.right);
        }
        // 如果x没有右孩子。则x有以下两种可能：
        // (01) x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。
        // (02) x是"一个右孩子"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，找到的这个"最低的父结点"就是"x的后继结点"。
        BSTNode<T> y = x.parent;
        while ((y != null) && (x == y.right)) {
            x = y;
            y = y.parent;
        }

        return y;
    }

    /**
     * 将节点插入二叉树
     *
     * @param bst 二叉树
     * @param z   插入的节点
     */
    private void insert(BSTree<T> bst, BSTNode<T> z) {
        int cmp;
        BSTNode<T> y = null;
        BSTNode<T> x = bst.mRoot;

        // 查找z的插入位置
        while (x != null) {
            y = x;
            cmp = z.key.compareTo(x.key);
            if (cmp < 0) {
                x = x.left;
            } else {
                x = x.right;
            }
        }

        z.parent = y;
        if (y == null) {
            bst.mRoot = z;
        } else {
            cmp = z.key.compareTo(y.key);
            if (cmp < 0) {
                y.left = z;
            } else {

                y.right = z;
            }
        }
    }

    /**
     * 插入数据
     *
     * @param key 要插入的数据
     */
    public void insert(T key) {
        BSTNode<T> z = new BSTNode<T>(key, null, null, null);
        insert(this, z);
    }

    /**
     * 删除节点并返回
     *
     * @param bst 二叉树
     * @param z   要删除的节点
     * @return 要删除的的节点
     */
    private BSTNode<T> remove(BSTree<T> bst, BSTNode<T> z) {
        BSTNode<T> x;
        BSTNode<T> y;

        if ((z.left == null) || (z.right == null)) {
            y = z;
        } else {
            y = successor(z);
        }
        if (y.left != null) {
            x = y.left;
        } else {
            x = y.right;
        }
        if (x != null) {
            x.parent = y.parent;
        }
        if (y.parent == null) {
            bst.mRoot = x;
        } else if (y == y.parent.left) {
            y.parent.left = x;
        } else {
            y.parent.right = x;
        }
        if (y != z) {
            z.key = y.key;
        }
        return y;
    }

    /**
     * 删除数据
     *
     * @param key 要删除的数据
     */
    public void remove(T key) {
        BSTNode<T> z, node;

        if ((z = search(mRoot, key)) != null) {
            node = remove(this, z);
        }
    }

    /**
     * 打印二叉搜索树
     *
     * @param tree      跟节点
     * @param key       数据
     * @param direction 层级
     */
    private void print(BSTNode<T> tree, T key, int direction) {
        // tree是根节点
        if (tree != null) {
            if (direction == 0) {
                System.out.printf("%2d is root\n", tree.key);
            }
            // tree是分支节点
            else {
                System.out.printf("%2d is %2d's %6s child\n", tree.key, key, direction == 1 ? "right" : "left");
            }
            print(tree.left, tree.key, -1);
            print(tree.right, tree.key, 1);
        }
    }

    /**
     * 打印二叉树
     */
    public void print() {
        if (mRoot != null) {
            print(mRoot, mRoot.key, 0);
        }
    }


    /**
     * 销毁二叉树
     *
     * @param tree 跟节点
     */
    private void destroy(BSTNode<T> tree) {
        if (tree == null) {
            return;
        }
        if (tree.left != null) {
            destroy(tree.left);
        }
        if (tree.right != null) {
            destroy(tree.right);
        }
        tree = null;
    }

    /**
     * 销毁二叉树
     */
    public void clear() {
        destroy(mRoot);
        mRoot = null;
    }

}
